There are many FPGA products of which the logic functions are reconfigurable. Patent documents 1 to 11 give exemplary structures of such FPGAs:
Patent Document 1: Published Japanese Translation of PCT Application 8-509344/1996 (Tokuhyohei 8-509344; published on Oct. 1, 1996)
Patent Document 2: Published Japanese Translation of PCT Application (Tokuhyo) 2001-519133 (published on Oct. 16, 2001)
Patent Document 3: U.S. Pat. RE 34,363 (published on Aug. 31, 1993)
Patent Document 4: U.S. Pat. No. 5,455,525 (published on Oct. 3, 1995)
Patent Document 5: U.S. Pat. No. 5,682,107 (published on Oct. 28, 1997)
Patent Document 6: U.S. Pat. No. 5,689,195 (published on Nov. 18, 1997)
Patent Document 7: U.S. Pat. No. 5,883,526 (published on Mar. 16, 1999)
Patent Document 8: U.S. Pat. No. 5,914,616 (published on Jan. 22, 1999)
Patent Document 9: U.S. Pat. No. 5,942,913 (published on Aug. 24, 1999)
Patent Document 10: U.S. Pat. No. 6,084,429 (published on Jul. 4, 2000)
Patent Document 11: U.S. Pat. No. 6,300,794 (published on Oct. 9, 2001)
As described in patent documents 1, 2, 5, 8, 9, the FPGA generally contains basic blocks as shown in FIG. 1a being arranged in a 2-dimensional array as in FIG. 4. The following will take the x-direction to be the lateral direction and the y-direction to be the longitudinal direction for descriptive purposes. A typical basic block includes wire channels 106, 107 which connect the block to other ones, a switch matrix 101 specifying paths, and a logic block 102 which contains reconfigurable logic elements and memory elements. The switch matrix 101 and the logic block 102 are connected via a wire 105. Wires 103 and a wire 104 also connect the basic block to other ones. The wires 103 connect it to an adjoining basic block. The wire 104 connects it to a basic block other than the next one.
FIG. 2 shows a concrete example of the logic block 102. In this example, the block includes lookup tables 202 as reconfigurable logic elements and D flip-flops 203 as memory elements. The lookup table 202 is provided in the form of a SRAM or other kind of memory. The output of the lookup table 202 and the D flip-flop 203 are fed back to the lookup table 202. The signals are also supplied to the switch matrix 101 via wires 105. Inputs from outside the basic block are also supplied to the lookup table 202 via the switch matrix 101 and the wires 105. Inputs to the lookup table 202 first go through programmable switches 201 provided to the lookup table 202. The switches 201 enables selection between the feedback inputs from the lookup table 202 and the D flip-flop 203 and inputs from outside the basic block via the wires 105. Some recent FPGAs include a logic block like the one in FIG. 2, but with an additional carry handling element. Some blocks are constructed entire of memory or multipliers.
FIG. 1b shows the topology of the switch matrix 101. The figure indicates by arrows the presence/absence of switches which connect the wire channel 106a located on the left hand side in terms along the x-direction to the wire channels 106b, 105a, 105b. In the 2-dimensional switch matrix 101, switches are needed which connects to wire channels in three directions. The figure shows only the connections from the wire channel 106a located on the left hand side along the x-direction to the remaining wire channels 106b, 105a, 105b; there exist switches, however, which connect each wire channel to the other wire channels.
The switch matrix 101 has switches shown in FIG. 3 to short-circuit wires which connect to basic blocks to the right/left/top/bottom, such as the wires 103 and wire 104 in FIG. 1a, with each other. The switch includes a multiplexer 301. The inputs of the multiplexer 301 are coupled to wires 303 which extend from wires connecting together the basic blocks to the right/left/top/bottom which connect to the switch matrix 101 and some of the wires 105 carrying outputs from the logic block 102. The inputs are selectively output to a tristate buffer 302. The buffer 302 drives one of wires, such as the wires 103 and the wire 104, which connect basic blocks to each other. The use of the tristate buffer 302 enables the wires to which its output is supplied (for example, wires 103) to be used in both directions. The tristate buffer 302 is can be replaced with an ordinary buffer. Furthermore, the switch may be arranged including no buffer at all. The switch is controlled by a SRAM or other memory.
The user makes suitable value settings in a switch-controlling memory and a lookup table-providing memory before use, so that the FPGA can operate as desired.
With shrinking feature sizes in semiconductor process technology, custom design is becoming a time consuming and expensive step. In contrast, the FPGA requires much less time and cost in logic function design because it is inherently reconfigurable. In addition, the FPGA has a regular structure to which the latest semiconductor process technology can be applied relatively easily. This is expected to contribute to greater integration. Newer semiconductor process technology is used with the FPGA than with the application specific integrated circuit (“ASIC”). The FPGA was primarily used as a prototype in its infancy. Equipped now with improved capabilities, it is gaining attention as a replacement for a DSP and small- and medium-sized ASIC. Its field of application is also expanding. The FPGA exhibits growing advantages with its shrinking feature size. The FPGA is expected to find applications in more new fields including mobile devices and digital household appliances.
A disadvantage of the FPGA is its extremely slow speed when compared to the ASIC because the FPGA wires extend passing through large numbers of switches. Another one is its extremely low logic density when compared to the ASIC because of the provision of the large numbers of switches in the FPGA. These problems become increasingly serious with greater integration which is inevitably accompanied by a long average wire length and a large wiring area. These problems need to be solved completely to realize a large scale FPGA.
To mitigate the situation, there is provided connecting wires which extend over some switch matrices like the wire 104 in FIG. 1a. The number of switch matrices over which the wires extend and the number of those wires need to be optimized carefully.
Another possible way to reduce the wires between the logic blocks 102 is to increase the grain size of the logic blocks 102. The logic block 102 in FIG. 2 includes two logic elements, each being a pair of a lookup table 202 and a flip-flop 203. Logic blocks including more logic elements (e.g., four) may be prepared. This is a similar structure to the FPGA having a hierarchical structure taught in patent document 6. Here, the FPGA as a whole is considered a superregion, and each basic block a subregion. The superregion has an ordinary 2-dimensional array structure. In a subregion, however, logic elements are equivalently connected together as in FIG. 2. The switch matrix is equivalently connected to each logic element in a subregion-superregion wire connection. In this structure, expansion of the subregion leads to large increases in switch counts and delays on internal wires.
These problems can be addressed by a modified design, like the segmentation of subregion internal wires as in patent document 7 and further hierarchization in the subregion as in patent document 11.
The window frame architecture disclosed, for example, in patent document 4 can be considered a kind of hierarchical structure. Here, connections in a subregion has a 2-dimensional array structure. Connections are made from the edges of a subregion to wire channels in a superregion. With this structure, expanding a subregion adds extra length to the wires of the superregion, which is only wasted. The problem can be addressed by a modified design in which wires in the superregion are segmented as in patent document 10, for example. The size of the subregion, connections in the subregion, etc. need to be optimized carefully also in wiring architectures based on the hierarchical structures.
Typical FPGAs are optimized with respect to these properties. It is however not clear whether the optimization will be effective in addressing future increases in wiring areas and delays of the FPGA. Accordingly, proposals are made for 3-dimensional FPGAs in, for example, non-patent documents 1 and 2 to solve problems relating to FPGA wiring.    Non-patent document 1: “Wiring Requirement and 3-dimensional Integration of Field-Programmable Gate Array,” A. Rahman et al., Proc. SLIP, 2001.    Non-patent document 2: “Rothko: A 3-dimensional FPGA,” M. Leeser et al., IEEE Design and Test of Computers, Vol. 15 (no. 1), pp. 16-23, 1998.
An example of a basic block in the 3-dimensional FPGA is shown in FIG. 5. The following will take the x-direction to be the lateral direction, the y-direction to be the longitudinal direction, and the z-direction to be the vertical direction of the chip. Wire channels 503 and 504 extend in the x and y-directions respectively. Another wire channel 506 extends in the z-direction. The wire channel 506 connects to a switch matrix 501 in a tile in an upper or lower layer. The switch matrix 501 and the logic block 502 in the basic block of FIG. 5 correspond respectively to the switch matrix 101 and the logic block 102 in the basic block in FIG. 1. FIG. 6a is a 3-dimensional view of the wires coupled to the switch matrix 501. FIG. 6b shows a topology for the switch matrix 501. To prevent the figure from becoming too complicated, the figure shows only the connections from a wire channel 503a located on the left hand side along the x-direction to wire channels 503b, 504a, 504b, 506a, 506b in other directions; there exist switches, however, which connect each wire channel to the other wire channels. Therefore, a switch matrix in the 3-dimensional FPGA needs switches connecting to five directions. Inside a switch matrix 501, each wire channel in each certain direction can connect to wire channels in all directions. FIG. 7 shows connections in a switch matrix 501 in the 3-dimensional FPGA.
In the structure, each basic block has an increased number of adjoining basic blocks. Connections between basic blocks travel through fewer switch matrices; wiring delays are thus reduced. In addition, the number of switches in the FPGA is in proportion to the number of tracks in a wire channel. (A wire channel is a bunch of wires. Each wire in the wire channel is called a track.) Connections are made to wire channels in three directions in a 2-dimensional switch matrix. In a 3-dimensional switch matrix, connections are made to those in five directions, and the number of switches per track increases. Since a large scale 3-dimensional FPGA needs much fewer tracks for wire channels than the 2-dimensional FPGA. The 3-dimensional FPGA has a higher logic density.
Non-patent document 1 states that an FPGA with 20k gates, if arranged 3-dimensionally in four layers, exhibits 45 to 60% less wiring delay and 20 to 40% greater integration of logic. The document also shows that improvements grow with increasing integration of logic. It is understood that the 3-dimensional integration is increasingly effective with greater scale FPGAs.
However, it is difficult to fabricate fine vertically running wires. The manufacture of the 3-dimensional FPGA, therefore, is extremely difficult. In addition, it is difficult for heat to radiate from 3-dimensional integrated circuits, and only a limited number of layers can be stacked. It is impossible to realize a 3-dimensional FPGA with sufficient integration in the foreseeable future.